﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/kth-missing-positive-number/
/*
题目描述：
给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
 
示例 1：
输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。

示例 2：
输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。

提示：
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

进阶：
你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗？
*/

// 方法1——暴力法
/*
思路：
直接枚举从1到arr[arrsize-1]的所有数字，对于每个数字，都在arr数组中寻找其是否存在
如果存在则跳到下一个数字，如果不存在则先让k--后在跳到下一个数字，当k减到0时，返回对应的数字即可。
若将从1到arr[arrSize - 1]的数字全都遍历完时k还未等于0，则返回arr[arrSize-1] + k。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int findKthPositive1(int* arr, int arrSize, int k) {
	assert(arr);
	int i = 0;
	int j = 0;
	int max = arr[arrSize - 1];
	for (i = 1; i <= max; i++) {
		for (j = 0; j < arrSize; j++) {
			if (arr[j] == i) {
				break;
			}
		}
		if (j == arrSize) {
			k--;
			if (0 == k) {
				return i;
			}
		}
	}
	return max + k;
}
// 时间复杂度：O(max*n)，max为数组中最大的数，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——双指针
/*
思路：
起初我们让两个指针p1和p2分别指向数组arr和数组arr2的起始位置，
这里的arr2所存储的是从1到arr[arrSize - 1]的所有数字。
如果arr[p1] == arr2[p2]，则让p1和p2都向后移动一位，
如果arr[p1] != arr2[p2]，则先让k--，再让p2向后移动一位。
当k为0时，直接返回对应的数字即可。
若将从1到arr[arrSize - 1]的数字全都遍历完时k还未等于0，则返回arr[arrSize-1] + k。
*/
// 有了以上思路，那我们写起代码来也就水到渠成了：
int findKthPositive2(int* arr, int arrSize, int k) {
	assert(arr);
	int p1 = 0;
	int p2 = 0;
	int max = arr[arrSize - 1];
	while ((p1 < arrSize) && (p2 <= max)) {
		if (arr[p1] == p2) {
			p1++;
			p2++;
		}
		else {
			k--;
			if (0 == k) {
				return p2;
			}
			p2++;
		}
	}
	return max + k;
}
// 时间复杂度：O(max)，max为数组中最大的数字，我们最多需要将数字1到arr[arrSize]都遍历一遍。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法3——二分查找法
/*
思路：
由于数组时严格升序的，所以对于每个arr[i]，我们都可以唯一确定到第i个元素为止缺少的数字个数为
arr[i] - (i + 1) = arr[i] - i - 1。
而且随着i的递增，arr[i] - i - 1只有可能增大或者不变，所以如果要把arr[i] - i - 1也当成一个序列的话，
这个序列也是有序的。
所以我们就可以使用二分法来查找，目标是找到第一个arr[i] - i - 1 >= k的情况。
而如果arr[arrSize - 1] - (arrSize - 1 + 1) < k的话，说明数组arr内丢失的数字还不够k个，
此时就可以直接返回arr[arrSize - 1] + (k - (arr[arrSize - 1] - (arrSize - 1 + 1) ) )
而对于需要返回的那个丢失的第k个数字，我们只需要算出arr[mid - 1] + (k - (arr[mid - 1] - (mid - 1 + 1)))即可
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int findKthPositive3(int* arr, int arrSize, int k) {
	assert(arr);
	// 特殊情况特殊处理
	if (arr[0] > k) {
		return k;
	}
	if (arr[arrSize - 1] - (arrSize - 1 + 1) < k) {
		return arr[arrSize - 1] + (k - (arr[arrSize - 1] - (arrSize - 1 + 1)));
	}
	int left = 0;
	int right = arrSize - 1;
	int mid = 0;
	while (left < right) {
		mid = left + (right - left) / 2;
		if (arr[mid] - mid - 1 < k) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return arr[left - 1] + (k - (arr[left - 1] - (left - 1 + 1)));
}
// 时间复杂度：O(logn)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。


